О НАДЕЖНОСТИ НЕВЕТВЯЩИХСЯ ПРОГРАММ 
В БАЗИСЕ, СОДЕРЖАЩЕМ ФУНКЦИЮ ВИДА x₁^a₁ V x₂^a₂ 

Грабовская Светлана Михайловна, ассистент, кафедра дискретной математики, Пензенский 
государственный университет, г. Пенза, swetazin@mail.ru

 519.718

Рассматривается реализация булевых функций неветвящимися программами с оператором условной остановки в полном конечном базисе B, содержащем некоторую функцию вида x₁^a₁ V x₂^a₂, a₁, a₂ из интервала {0.1}. Предполагается, что функциональные операторы с вероятностью ε(ε из интервала (1,0/2)) подвержены инверсным неисправностям на выходах, а операторы условной остановки абсолютно надежны. Доказано, что любую булеву функцию ƒ можно реализовать неветвящейся программой, функционирующей с ненадежностью не больше ε+81ε² при ε из интервала (0,1/960]

булевы функции, неветвящиеся программы, оператор условной остановки, синтез, надежность

 Скачать статью в формате PDF

1. Чашкин, А. В. О среднем времени вычисления значений булевых функций / А. В. Чашкин // Дискретный анализ и исследование операций.  1997.  Январь–март.  Т. 4.  № 1.  С. 60–78.
2. Алехина, М. А. О надежности схем в базисах, содержащих функции не более чем трех переменных / М. А. Алехина, А. В. Васин // Ученые записки Казанского государственного университета.  2009.  Т. 151.  Кн. 2.  С. 25–35.  (Физико-математические науки).
3. Васин, А. В. Асимптотически оптимальные по надежности схемы в полных базисах из трехвходовых элементов : дис. … канд. физико-математических наук / Васин А. В.  Пенза, 2010. 100с. 
4. Васин, А. В. Об асимптотически оптимальных схемах в базисе / А. В. Васин // Дискретный анализ и исследование операций.  2009.  Ноябрьдекабрь.  Т. 16.  № 6.  С. 12–22.